package leetcode.easy.q14;

/**
 * 最长公共子串
 */
public class ExtendedQuestion {
    public static void main(String[] args) {
        System.out.printf(new Solution4LongestSubStr().longestCommonSubstring(new String[]{"sssass","aasasaa"}));
    }
}

/**
 * 1.找到最短的str
 * 2.用最短的str作为模式去匹配
 */
class Solution4LongestSubStr {
    public String longestCommonSubstring(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        int shortestStrIndex = 0;

        //找到最短的str
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() < strs[shortestStrIndex].length()) {
                shortestStrIndex = i;
            }
        }
        if (strs[shortestStrIndex].length() == 0) {
            return "";
        }
        String target = strs[shortestStrIndex];
        String longestResult = "";
        StringBuilder sb = new StringBuilder();
        int[] pre = new int[strs.length];
        for (int start = 0; start < target.length(); ) {
            char c = target.charAt(start);
            boolean notMatch = false;
            for (int j = 0; j < strs.length; j++) {
                boolean foundC = false;
                //第j个字符串,初始匹配定位，后续匹配则相邻比较
                if (sb.length() == 0) {
                    while (pre[j] < strs[j].length()) {
                        if (strs[j].charAt(pre[j]) == c) {
                            //c在第j个字符串中找到，match！
                            foundC = true;
                            break;
                        } else {
                            pre[j]++;
                        }
                    }
                } else {
                    if (pre[j] < strs[j].length()) {
                        if (strs[j].charAt(++pre[j]) == c) {
                            foundC = true;
                            break;
                        }
                    }
                }

                if (!foundC) {
                    //遍历完第j个String，找不到c，则c的匹配结束
                    notMatch = true;
                }
            }
            //如果遇到一个字符不再匹配，则判断当前子串是否比之前的结果更长，否则丢弃，并开始新的子串匹配
            if (notMatch) {
                if (sb.length() > longestResult.length()) {
                    longestResult = sb.toString();
                }
                pre = new int[strs.length];
                sb = new StringBuilder();
            } else {
                sb.append(c);
            }
            start++;
        }
        return longestResult;
    }
}